This application contains a computer program listing appendix on a compact disc, which is fully incorporated herein by reference. The compact disc contains a single file named xe2x80x9cAppendix.txtxe2x80x9d of size 36,352 bytes created on Nov. 10, 2000.
A portion of this disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all United States and International copyright rights whatsoever.
The present invention relates to assigning identifiers in cellular wireless networks. More specifically, it relates to a method for assigning pseudo-random offset numbers to the sectors of a code division multiple access wireless system so as to minimize the interference between base stations.
Cellular wireless is an increasingly popular means of personal communication in the modern world. People are using cellular wireless networks for the exchange of voice and data over cellular telephones, Personal Digital Assistants (xe2x80x9cPADsxe2x80x9d), cellular telephone modems, and other devices. In principle, a user can seek information over the Internet or call anyone over a Public Switched Telephone Network (xe2x80x9cPSTNxe2x80x9d) from any place inside the coverage area of the cellular wireless network.
A typical cellular wireless network is divided into cells, each providing wireless service to a particular area of terrain within the coverage area of the network. Each of the cells has a base station with a radio transceiver that communicates with mobile stations within the cell. Where to place a cell""s base station is a function of the expected capacity of calls within the cell. Additionally, the signal power of the base station may depend on the proximity of other base stations. Cell sizes may therefore vary considerably.
The effective coverage area of any cell depends on many factors influencing propagation. Such factors include antenna height, cell topography, geography, and clutter. For example, one cell may cover a large area because it has an antenna on a tall building while another cell may cover only a small area because signals from the base station have to navigate several intervening buildings. Other cells may cover long sections of a highway. To increase the number of mobile stations that can transmit simultaneously within any cell, i.e. increase the capacity of the system, each cell may be further divided into sectors. If a cell is divided into sectors, the division is typically into three sectors, each sector providing an approximately 120-degree coverage of the cell. To avoid ambiguities when handing off to another cell, a mobile station must communicate with only one sector at any point in the cellular wireless network. Therefore each sector must uniquely identify itself to any mobile station at any given point in the network.
As is familiar to those of ordinary skill in the art, in the Advanced Mobile Phone System (xe2x80x9cAMPSxe2x80x9d), a dominant cellular telephone system of the last century, each sector transmits on a unique group of frequencies. In AMPS, each mobile station within the coverage area of the sector communicates with the base station on only one of these frequencies in the group. By transmitting on different frequencies, the communications from two mobile stations do not interfere with each other. AMPS, however, has two important drawbacks. One drawback is that it has limited capacity because there is a finite number of available frequencies that have to be distributed among the sectors of the AMPS network without neighboring cells sharing a common frequency. Another drawback is inefficient use of the channel defined by each frequency, because the communication typically includes dead times, when either the base station or the mobile station is silent.
Cellular telephone systems are presently undergoing an evolution to digital. Digital systems may overcome the drawbacks of the older AMPS services. Some of the digital wireless systems use time division multiple access (xe2x80x9cTDMAxe2x80x9d) technology or code division multiple access (xe2x80x9cCDMAxe2x80x9d) technology to permit multiple users to converse simultaneously on the system without interference from each other. Typical formats for TDMA transmission include those described in the interim standards IS-54B and IS-136, which are incorporated herein by reference. These standards are published by the Telecommunications Industries Association/Electronic Industries Association (xe2x80x9cTIA/EIAxe2x80x9d). Typical formats for CDMA transmission include those described in the ANSI/TIA/EIA-95-B-99 (xe2x80x9cANSI-95xe2x80x9d) standard, which is fully incorporated herein by reference. Typical CDMA systems include the xe2x80x9cSprint PCSxe2x80x9d system provided by the Sprint Communications Company of Westwood, Kansas. TDMA and CDMA systems typically have increased call capacity and more efficient use of bandwidth.
In present TDMA systems, each mobile station within a sector transmits in a unique time slot and thus its signal is interleaved with signals from other mobile stations within the sector. The TDMA system typically fills a time slot corresponding to a silent periods with signals from another active mobile station, thus increasing the data transmission efficiency of the cellular network. The base stations, however, still transmit and receive on a similar group of frequencies as AMPS. Prudence still dictates that if the same frequency is used by two or more sectors, due to a limited number of available frequencies, then these sectors ought to be as far apart as possible to minimize confusing a mobile station about the identity of the base station with which it is communicating.
CDMA systems warrant similar prudence. In present CDMA systems, data modulates a noise-like carrier and spreads the spectrum over the available bandwidth. CDMA systems require less transmitter power compared to other cellular telephone systems and thus allow mobile stations to carry less battery bulk. Additionally, the spreading helps prevent interference with the signal, deliberate or otherwise, and also helps prevent the interception of calls. To intercept a call, an eavesdropper would need a precise copy of the unmodulated noise-like carrier. Typically, the noise-like carrier comprises a series of pseudo-random numbers (xe2x80x9cPNsxe2x80x9d) generated by a computer algorithm. Given a seed, the computer algorithm generates a precise and reproducible series of numbers that appear random; a typical CDMA system requires the generation of a series with at most 256 PNs.
Each sector has a single PN for identifying itself to mobile stations. During configuration of the CDMA system, a technician may assign one of the PNs to each sector to distinguish it from the others. More typically, the technician assigns another number, a PN offset number, to the sector. The PN offset number represents where a particular PN appears in the generated series. Given the PN offset number and the seed, the sector may deduce the PN by iterating the generating algorithm. Therefore the technician typically assigns a PN offset number to each cell to identify the sector to the mobile stations.
But, similar to the drawbacks of the AMPS network, the number of sectors in a CDMA network can exceed the number of unique PN offset numbers: for example, as stated above, some CDMA systems may support a maximum of 256 PN offset numbers. Thus some PN offset numbers may be assigned to more than one sector, as was the case with frequency groups for TDMA Systems. Although each base station identifies itself with a single PN offset number rather than multiple frequencies as used in the TDMA systems, prudence again dictates that sectors with the same PN offset numbers ought to be as far apart as possible to reduce confusion at the mobile stations.
In summary, identifiers may need to be reused within the cellular wireless system, and this reuse creates problems of distributing the identifiers throughout the network. This problem exists whether the identifiers are frequencies for a TDMA system or PN offset numbers for a CDMA system. The transceivers in the cells hand-off a connection to a mobile station between the cells and between the sectors in the cells. But the ability to hand-off the call between sectors and cells requires that the identifiers must be unique for all signals at any given point in the network. Thus a technician faces the task of assigning the identifiers in such a way that the signals from different sectors with the same identifier do not interfere.
Merely assigning different identifiers to adjacent sectors may avoid some ambiguities when a mobile user is handed-off from one sector to another. Some sectors, however, may cover a large area and therefore have a large number of adjacent sectors that cover small areas. Outside these small adjacent sectors may also be other small sectors, and thus the large sector""s base station may equally receive signals from many more sectors than just the adjacent sectors. The technician therefore must assign reused identifiers to sectors that are as far apart as possible to reduce interference. In the case of CDMA systems, the technician has to assign the PN offset numbers with as much space as possible between sectors with the same PN offset number.
It is therefore desirable to provide a method for assigning a set of identifiers amongst multiple sectors such that the distance between reused identifiers is sufficiently large to reduce interference between sectors.
In accordance with preferred embodiments of the present invention, some of the problems associated with allocating identifiers to sectors in a cellular wireless network are overcome. The cellular wireless network has a plurality of cells and provides cellular wireless service to a plurality of geographical regions. Each geographical region is associated with a corresponding cell of the plurality of cells and includes a base station for transmitting and receiving wireless communications to and from a mobile station. The plurality of cells further comprises a plurality of sectors, each of which is associated with an identifier chosen from a plurality of identifiers to identify itself to the mobile station. One aspect of the invention includes a method for allocating the plurality of identifiers to the plurality of sectors to reduce interference between base stations.
An exemplary method includes determining, for each sector of the plurality of sectors, a measure of neighbor density for the sector. The plurality of sectors is ranked according to the measure of neighbor density to produce a first ranking of sectors ranging from a first sector with highest neighbor density to a second sector with lowest neighbor density. For each sector of the plurality of sectors in order of the first ranking beginning with the first sector, an identifier is allocated to the sector. An exclusion range is evaluated for each sector. The exclusion range is a measure of minimal distance between the sector and other sectors having the same allocated identifier. The plurality of sectors is re-ranked according to the exclusion range to produce a new ranking of sectors ranging from a third sector with least exclusion range to a fourth sector with greatest exclusion range. During the re-ranking of the plurality of sectors, each sector of the plurality of sectors retains the identifier that was previously allocated to the sector. The identifier for each sector is reallocated in order of the new ranking beginning with the third sector. The evaluating step, the re-ranking step, and the reallocating step are repeated until each sector of the plurality of sectors retains the identifier that was previously allocated to the sector.
For example, the method of the present invention may provide a preferred assignment of PN offset numbers to the sectors of a CDMA cellular wireless network. The preferred assignment may help to assure that the cellular network does not present an ambiguity to any mobile station in the network. With the benefit of the preferred assignment, any mobile station may not receive signals of similar strength from more than one sector having a particular PN offset number. Hence the method described herein may allow the CDMA network to seamlessly hand off mobile telephones to the appropriate sector.
The foregoing and other features and advantages of preferred embodiments of the present invention will be more readily apparent from the following detailed description, which proceeds with references to the accompanying drawings.